/**
 * 数组异或和的定义:把数组中所有的数异或起来得到的值
 * 给定一个整型数组arr，其中可能有正、有负、有零，求其中子数组的最大异或和
 * 【举例】
 * arr = {3}
 * 数组只有1个数，所以只有一个子数组，就是这个数组本身，最大异或和为 3
 * <p>
 * arr = {3,-28,-29，2]
 * 子数组有很多，但是{-28，-29}这个子数组的异或和为7，是所有子数组中最大的
 *
 * @author Liaorun
 */
public class MaxEOR {

    public static void main(String[] args) {
        System.out.println(maxEOR1(new int[]{3}));
        System.out.println(maxEOR1(new int[]{3, -28, -29, 2}));
        System.out.println(maxXorSubarray(new int[]{3}));
        System.out.println(maxXorSubarray(new int[]{3, -28, -29, 2}));
    }


    public static int maxEOR(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        // 尝试必须以arr[i]结尾的子数组,最大异或和是多少，尝试所有的arr[i]
        int ans = 0;

        for (int i = 0; i < arr.length; i++) {
            // 必须以arr[i]结尾
            // 0..i 每一个开头
            for (int start = 0; start < i; start++) {
                // arr[start..i]这个子数组
                int sum = 0;
                for (int index = start; index <= i; index++) {
                    sum ^= arr[index];
                }
                ans = Math.max(ans, sum);
            }
        }

        return ans;
    }


    public static int maxEOR1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }


        // preSum[i] = arr[0..i]的异或和
        int[] preSum = new int[arr.length];
        // 第一个位置的异或和就是原数组第一个位置的值
        preSum[0] = arr[0];

        for (int i = 1; i < arr.length; i++) {
            // 当前位置的值 = 当前数组的值 ^ 前面所有数的异或和
            preSum[i] = arr[i] ^ preSum[i - 1];
        }

        // 尝试必须以arr[i]结尾的子数组,最大异或和是多少，尝试所有的arr[i]
        int ans = 0;

        for (int i = 0; i < arr.length; i++) {
            // 必须以arr[i]结尾
            // 0..i 每一个开头
            for (int start = 0; start <= i; start++) {
                // arr[start..i]这个子数组
                int sum = preSum[i] ^ (start - 1 == -1 ? 0 : preSum[start - 1]);

                ans = Math.max(ans, sum);
            }
        }

        return ans;
    }


    public static class Node {
        /**
         * 最多两条路可以走 0 or 1
         */
        public Node[] nexts = new Node[2];
    }

    /**
     * 把所有前缀异或和，加入到NumTrie,并按照前缀数组织
     */
    public static class NumTrie {
        public Node head = new Node();


        public void add(int num) {
            Node cur = head;
            // 把个32为整数的每一位取出，放到前缀树中
            for (int move = 31; move >= 0; move--) {
                int path = ((num >> move) & 1);
                // 原来没有树就新建，有就不变
                cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
                // 向下走一步
                cur = cur.nexts[path];
            }
        }

        /**
         * sum 最希望遇到的路径，最大的异或结果返回 O(32)
         *
         * @param sum arr 中 0..i的异或和
         * @return arr中以i位置为结束点的子数组，能得到的最大异或和
         */
        public int maxXor(int sum) {
            Node cur = head;
            // 最新的结果（sum ^ 走最优选择的路）所得到的值
            int res = 0;
            for (int move = 31; move >= 0; move--) {
                // 当前位如果是0，path就是整数0
                // 当前位如果是1，path就是整数1

                // num第move位置上的状态提取出来
                int path = (sum >> move) & 1;

                // sum 该位的状态，最期待的路
                // 是否是符号位 ？ 和path相等 ： 和path不等
                // example1 : best = 31 == 31 ? 1 : (1 ^ 1) = 1
                // example2: best = 30 == 31 ? 1 : (1 ^ 1) = 0
                int best = move == 31 ? path : (path ^ 1);

                // best: 最期待的路 -> 实际走的路
                // 期待的路没有，只能走另一条
                // question: 为什么一定有另一条路? answer: 因为添加的时候是从头添加到第32层的，能走到当前节点，说明肯定存在一条路到叶节点
                best = cur.nexts[best] != null ? best : (best ^ 1);

                // path num第move位的状态，best是根据path实际走的路
                res |= (path ^ best) << move;

                // 向下走一步
                cur = cur.nexts[best];
            }

            return res;
        }
    }


    public static int maxXorSubarray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;

        // 一个数都没有时候，异或和为0
        int sum = 0;
        NumTrie numTrie = new NumTrie();
        // question:为啥一开始要添加一条全为0的路？ answer:因为arr第一个位置的树的最优选择路径是，因为开始没有路径不能选择，所以添加一条默认路径
        numTrie.add(0);
        for (int i = arr.length - 1; i >= 0; i--) {
            // eor -> 0..i 异或和
            sum ^= arr[i];
            // i为结束点的子数组的异或和是否能刷新最大值
            max = Math.max(max, numTrie.maxXor(sum));
            // 添加一条路
            numTrie.add(sum);
        }

        return max;
    }

    public static int comparator(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return 1;
    }
}
